package C054;

import java.util.Arrays;

/**
 * ClassName: C01
 * Package: C054
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/3/30 00:46
 * @Version 1.0
 * @Since 1.0
 */
public class C01 {
    public static void main(String[] args) {
//        int[] arr = {1,3,-1,-3,5,3,6,7};
        int[] arr = {1, -1};
        maxSlidingWindow(arr,1);
        System.out.println(Arrays.toString(res));
    }


    static int n, MAXLEN = 100001, l = 0 , r = 0;
    static int[] res ;

    static int[] queue = new int[MAXLEN];
    public static int[] maxSlidingWindow(int[] nums, int k) {
        l = r = 0;
        Arrays.fill(queue,0);
        n = nums.length;
        res = new int[n - k + 1];

        // 补全 k -1 窗口的队列的信息
        for (int i = 0; i < k - 1; i++) {
            while(r > l && nums[i] >= nums[queue[r - 1]]) {
                r --;
            }
            queue[r++] = i;
        }

        for (int i = k - 1; i < n; i++) {
            while(r > l && nums[i] >= nums[queue[r - 1]]) {
                r --;
            }
            queue[r++] = i;
            res[i - k + 1] = nums[queue[l]];
            if(queue[l] == i - k + 1) {
                l ++;
            }
        }
        return res;
    }
}
